\documentclass[a4paper,10pt]{IEEEconf}
\usepackage[latin1]{inputenc}
\usepackage[american]{babel}
%\usepackage[T1]{fontenc}
\usepackage[dvips,pdftex]{graphicx}
%\usepackage{multicol}
\usepackage{subfigure}
\usepackage{named}
%\usepackage{fancybox}
%\usepackage{natbib}
\bibliographystyle{named}
\usepackage[dvips,pdftex]{hyperref}
%opening
\title{Symbol Recognition using Particle Swarm Algorithms}
%\title{A Study on Using Particle Swarm Algorithms in Symbol Recognition }
\author{Maha El Meseery,  Mahmoud Fakhr El Din,  Samyah Mashaly,
\\  Magdah Fayek,  Nevin Darwish}
\begin{document}
\maketitle
\begin{abstract}
Sketch recognition is defined as the process of identifying symbols that users draw using single or multiple strokes. Users draw strokes using a pen and the system should immediately interprets their strokes into objects that can be easily manipulated. This paper uses Particle Swarm Algorithm (PSO) to divide the strokes the user draws into meaningful geometric primitives. These geometric primitives are grouped to formulate symbols which are further identified. The results show that using PSO improves segmentation results which guide the symbol recognition phase. This paper uses SVM classifier which further improves the final recognition accuracy.  %u Final recognition has improved accuracy after the PSO algorithm using a SVM classifier.  
 %Hand drawn sketches are the natural method of exchanging thoughts between engineers and humans in general. Nevertheless, researchers barely give attention to improve current gesture and sketch recognition systems. In a sketch understanding system, users need to feel the freedom of paper and pencil along with the flexibility of computer manipulation. 
\end{abstract}
\section{Introduction}
%A picture speak a thousand words is also true for sketches. 
Scientists generally and engineers specifically express thoughts and designs using sketches. Engineers use sketches to exchange designs as a natural method of communication rather than writing or speaking. Engineers use paper and pencil design in early stages of design. Design engineers need a powerful computer based system with symbol recognition to help them design, manipulate and store sketches more effectively than using only papers. Increasing the interaction between computers and users in sketch and CAD systems has been the reason for the emerging of few advanced sketch recognition systems \cite{CAD}. Sketch recognition system converts the drawings and informal graphs user draws into objects and symbols that can be used in further interaction with the system. 

Sketch recognition is divided into four main steps preprocessing, segmentation, symbol recognition and finally sketch understanding. The preprocessing process saves user input stroke points from the hardware and collects basic information about the stroke then proceeds to remove noise and primary data calculation. In segmentation phase, the system divides the stroke into a set of simple geometrical primitives or segments. The third phase, sketch recognition, is clustering strokes and segments to formulate symbols that can be recognized by a classifier system. Finally, the sketch understanding phase uses priori information about the sketch to support identification of symbols by excluding any possible invalid symbols. 
%the basic symbols are identified in consistent with the whole sketch. \\
%from the user information from the users converts the strokes the user draw into segments which is recognized into basic symbols that can be easily manipulated. Finally, the basic symbols are interpreted in consistent with the whole sketch. \\
This paper introduces a sketch recognition system. The presented system uses' particle swarm algorithm (PSO) to optimally segment users strokes. Users can draw symbols using any number of strokes in any order they like. The system segments stroke user draws then cluster symbols together then passes them to the SVM symbol recognizer. The experiments in section \ref{sec:Experiments} shows that the proposed system improves the final symbol recognition accuracy. 

The remaining of this papers is organized as following; section \ref{Sec:RelatedWork} provides a brief literature review.  Section \ref{PSO} explains the general particle swarm algorithm which is used in the presented system. The proposed system block diagram along with a detailed system description is presented in Section \ref{Sysdisc}.  The experiments and results achieved are explained in Section \ref{sec:Experiments}. Finally, section \ref{ConclusionandFutureWork} states the conclusion and future work. 
%The next section will relate previous work in the field. The remaining of the paper will be as following; Section \ref{PSO} will explain the general particle swarm algorithm. Section \ref{Sysdisc} will describe the system block diagram and then section \ref{Prepross} will explain the preprocessing step, section \ref{seg} will describe the segmentation algorithm in details. Finally, section \ref{sec:Experiments} will describe the experiments that was preformed.\\
\section{Literature Review}
\label{Sec:RelatedWork}
%%%What is sketch recognitions. Why we need sketch recognition systems. 
The field of symbol recognition has gained interest in the last few years. A wide variety of techniques were used either on segmentation process or symbol recognition.
%To segment strokes
%In order to segment strokes, \cite{meanshift10} introduced a feature area for each primitive and then computed the segmentation error for different types of primitives based on this area.  %\citeauthor{HeloiseBeautification} used a dynamic programming algorithm to solve the segmentation problem \cite{HeloiseBeautification}. 
A hybrid algorithm was introduced in \cite{earlyprocess} where they generated different sets of segmentation based on both curvature and speed dominant points, this is followed by choosing a segmentation with the least error from generated hybrid set. Their system has a draw back as it only recognizes simple specific shapes with a set of low level recognizers. \cite{meanshift10} introduced a feature area for each primitive and then computed the segmentation error for different types of primitives based on the computed feature area. Their system achieved good accuracy in simple shapes (square, ellipse,...) but did not perform well in more complex shapes\cite{meanshift10,Paleosketch08}. \citeauthor{Paleosketch08} \cite{Paleosketch08} introduced a set of low level recognizers that were reported to achieve 98\%  accuracy but their system similar to all low level recognizers only identify a small set of simple shapes. 

Many different approaches have been investigated to achieve final recognition of symbols. Graph searching and template matching where used in \cite{GraphBased07} where a graph of the drawn symbol is generated and matched with a stored set of graphs templates to reach a classification decision. These systems may generate good performance but they are very computationally expensive. Geometrical and spatial descriptive language was used in \cite{SketchRead2007,Ladder30} where an architecture similar to compiler was used to recognize symbols. The drawback of this architecture is that the recognition system can only parse symbols that were hard coded using the descriptive language. New symbols are not recognized unless the description of the symbol is provided or generated using another system.  %%SVM and HMM classification was implemented in\cite{SVM300,HMM53} to correctly classify symbols.

Genetic algorithm was used by \cite{CruveDivisionSwarm} to optimally divide digital curves into lines and curves. \citeauthor{CruveDivisionSwarm} uses digital curves scanned from paper as input to the system and did not take advantage of the curvature or local geometric properties of the digital curve. \citeauthor{PolygonApproximationPSO} \cite{PolygonApproximationPSO} used PSO to convert digital curves into polygons, our system adopts \citeauthor{PolygonApproximationPSO} method but improves it by adding curvature and other local information while segmenting strokes to achieve better segmentations. The next section presents the general particle swarm algorithm which is used in our proposed segmentation algorithms. % are presented in section \ref{subsubsec:Discreteparticleswarmalgorithm}
% Other techniques as  [ ] was used  in []. \\  
%In the next section the particle swarm algorithm will be explained. After that the system block description and detailed algorithms will be described. We will then proceed to describe the experiments preformed and the achieved results.  
%\subsection{Sketch Recognitions systems}
%Details of Sketch systems. 
%Related work and research in this area. 
%Writing on the pros and cons of current systems.  
%Write on the difficulties of the sketch recognition systems. 
  %Some tried to detect dominant or corner points based on data generated from speed   \cite{earlyprocess} and mostly used curvature of the stroke drawn \cite{earlyprocess,meanshift10}. 
%Particle swarm algorithms was used in \cite{} to fit a set of points into ellipse or higher order curves.
%The first set of features introduced to be used on gesture recognition was introduced by Rubine in \cite{gestureexample12}. later,  Spatial relations and features where used in  \cite{cognitivesketch18,SRGraph57}  . \citeauthor{GeometryAndDomain102} introduced ink density feature which they used.  The use of Zernike moments  was used  as the only features to the SVM classifiers in \cite{HeloiseBeautification}.  \cite{SketchRead2007} used a set of features varied from relative spatial features and some compositional features.  \\
%After segmentation researchers varies on the methods in which to continue.
\section{Particle Swarm Algorithm}
\label{PSO}
%What is particle swarm algorithm and how it was used in related researches. 
The main idea of Particle Swarm Algorithm (PSO) is to represent each agent with a particle from the solution space. Each agent moves the particle with a direction and velocity based on equation \ref{eq:Swarm}.
 %Equation [\ref{eq:Swarm}] shows how velocity and direction of each particle are computed
 \begin{equation}
v_{ij}  = v_{ij}  + c_1 r_1 (lbest_{ij}  - p_{ij} ) + c_2 r_2 (gbest_{ij}  - p_{ij} )
\label{eq:Swarm}
\end{equation}
 where $r_1$ \& $r_2$ are random variables and $c_1$ \& $c_2$ are the swarm system variables.
\begin{equation}
%\[
p_{ij}=p_{ij}+v_{ij},
%\
\end{equation}
where $p_{ij}$ represent the $jth$ particle in the $ith$ agent and $v_{ij}$ is the velocity of the $jth$ particle in the $ith$ agent. After each iteration the global best $g_{best}$ particle and the agent local best $l_{best}$ particle are evaluated based on the maximum fitness functions of all particles. The solution is found after achieving a specific number of iteration or after an error threshold is achieved.
The following equation \ref{eq:descrite}  
\begin{equation}
   P(i)\Leftarrow 
\{
\begin{array}{c} 
1 \quad \quad if\quad r_{3}>t  \\

0 \quad \quad if\quad r_{3}<t 
\label{eq:descrite}
\end{array}\}
\end{equation}
 (where $t$ is a threshold and $r_{3}$ is a random variable), is used in order to change the general swarm algorithm into binary particle which handles particle values of either $0$ or $1$. 
    
\section{System Details}
\label{Sysdisc}
%The stroke is the path of points from the instant the pen is down till it is up.
Figure \ref{fig:Blockdiagram} shows that the main system blocks are 1) preprocessing, 2) segmentation, 3) clustering, 4) feature extraction, and finally 5) classification. 

 %Due to sloppiness of users and hardware glitches the system preprocess the data before further processing. 
The preprocessing phase is responsible of capturing the input data and removing the noise from it. The system then proceeds to estimate a set of possible dominant points to help in the segmentation process. % The time differences, direction, speed and curvature of all points of the stroke is computed along with some other geometrical data. The system then proceed to estimate a set of possible dominant points to help in segmentation process.  \\
  %then passes through the segmentation process which will try to 
  
 %The goal of the segmentation stage is to divide stroke into segments of either curves or lines.
The segmentation is divided into two steps ellipse fitting and curve segmentation. In the first step, the ellipse fitting process tries to fit the stroke into an ellipse. If the system fails, it passes the stroke to the second step; curve segmentation which consists of two PSO segmentation algorithms. The two algorithms generate two segmentations. The system then chooses the segmentation that has the minimum segmentation error.%generate the segmentations,  the minimum error will be the chosen segmentation. % is the ellipse fitting

 %the stroke first If the ellipse detection fails the stroke is passed to the segmentation algorithms which will pass it to the two PSO algorithms described below the segmentation with the minimum error will be the chosen segmentation.  The segmentation is then added to the set of un-recognized segments in the system. \\% This part is repeated for each stroke. 
 The clustering algorithm starts to group segments together after the segmentation step. The system allows the user draws the symbol by using any number of strokes; a set of unrecognized segments is passed to the clustering algorithm to generate a symbol and compute a feature vector for it. A set of hybrid features of statistical, geometric and spatial features is used to generate the symbol feature vector. The final classification step, SVM classifier uses the feature vector computed to classify the segments into one of the previously trained classes. The following sections provides a detail description of each step.%  Or to determine the symbol of the given segments from the set of preciously trained symbols. 
 %with a symbol from the training set.% The system compute composite set of features some are statistical other are spatial features based on the type primitives. Finally, the strokes are classified into the corresponding classes.% the classifier identifies the strokes into a symbol from the set of known symbols.\\
 
\begin{figure}[]
%\begin{minipage}[b]{0.5\linewidth}
	\centering
		\includegraphics[scale=0.75]{images/block2.pdf}%Blockdiagram.pdf}
	\caption{The system Block Diagram.} The figure shows the main system blocks. Preprocessing, segmentation, clustering, features extraction and classification. 
	
	\label{fig:Blockdiagram}
%	\end{minipage}
\end{figure}

\subsection{Preprocessing}
\label{Prepross}
%Some data is extracted from the points in the stroke.
 It is noted that as the user draws a shape, the pen slows down near corners and picks up speed when drawing a straight lines. Therefore, the speed and time difference data were widely used in sketch understanding systems \cite{earlyprocess}.  The direction and curvature data are used to determine the points with high angular changes along the path of points \cite{meanshift10}.  
 %speed is calculated as 
 In the presented system, we computed time difference, direction, speed and curvature of each point along the stroke. The speed is calculated as  $v=\Delta t/\Delta s$ where $t$ is the time difference between two points and $s$ is the length between them. The direction is calculated as the angle between two vectors and curvature is considered as the change in direction with respect to length i.e. $c= \Delta d/\Delta s$.
 
 %system compute speed, distance data for all points in the stroke. Curvature is computed using estimation used in [] where direction computed is angle between two lines. Curvature is 
 %$\Delta d/  \Delta S $ where d is the difference direction of point and s is difference in distance between points. 
 It should be noted that, all these calculations are performed in real time while the user draws the strokes. The complexity of computation is $O(n)$ where $n$ is number of points. \\
 Figure \ref{fig:speed2} shows the computed data for the stroke drawn in fig. \ref{fig:orignalStroke}. %If you look at the data curves you will see by looking at the data curves s
 It is noted that the dominant points are characterized by lower speed values and higher curvature and direction values (fig. \ref{fig:speed2}). \\% the lower speed points correspond to vertex and dominant point's location. The higher the direction and curvature data correspond to location with higher change in curvature witch promote the location for vertices. \\
After the system computes all the speed, time difference and curvature data it proceeds to detect the points with low velocity and high curvatures. Using simple differentiations to detect local extreme points resulted in false points due to the non smooth curves. Hence, the system adopted a process presented by \cite{earlyprocess}, where the mean
%So instead the following procedure was used, firstly the mean of the curve is used as threshold for lower values then the high values are further investigated to find the extreme points. Hence, the mean 
of the curve is calculated and used as threshold \textit{th}. The threshold \textit{th} is used to separate the curve into regions  $Region_i$; each region $Region_i$ is defined as the part between two intersection points of the threshold line and the curve. Regions higher than the threshold \textit{th} are processed to find the maximum point $Max(Region_i)$ of each region $Region_i$. The stroke points $p_i(x,y)$ that correspond to those maximum values are labeled as \textit{possible dominant points} $P_{pd}$.   \\
   %If we tried to differentiate the curve the result will be false threshold values we divide the data into regions of data higher or lower that the threshold. This will let us only look for high data only. The maximum of each region is then computed and reported as a possible vertex point. 
\begin{figure}[]
	\centering
		\includegraphics[scale=0.5]{images/orignalStroke.pdf}
	\caption{Stroke Sample} An example of the stroke drawn in the system.
	\label{fig:orignalStroke}
\end{figure}
The system repeats this process to curvature, time difference and speed curves. All the points labeled as possible dominant points $P_{pd}$ are saved into a single array. They are then used as input to guide the next segmentation phase. 
\begin{figure*}[]
%\begin{minipage}[b]{0.9\linewidth}
	\centering

		\subfigure[ The Speed of data] {\includegraphics[scale=0.25]{images/speed2.pdf}}	
	%	\subfigure[ Direction ] {\includegraphics[scale=0.15]{images/direction2.pdf}}
					%\end{minipage}
					\hspace{20 mm}
					%\begin{minipage}[b]{0.5\linewidth}
			\subfigure[The Curvature] {\includegraphics[scale=0.29]{images/curvature2.pdf}}
	%		\subfigure[ Time Difference] {\includegraphics[scale=0.15]{images/time2.pdf}}
%			\end{minipage}
	\caption{Data Curves} The curve in a) shows the speed of the points in stroke in fig. \ref{fig:orignalStroke}. b) Shows the curvature curve for the same stroke.  %{The data of the stroke}
	
	\label{fig:speed2}
\end{figure*}
%Description of input data. 
%how to calculate speed, curvature, area, bounding box.
%how to remove noise. 
%Finally how to compute primarily dominant points. 
\subsection{Segmentation}
\label{seg}
After computing the primary data the system tries to segment the stroke into a set of primitives. The segmentation algorithm first attempts to detect if the stroke is an ellipse. If the stroke proved to be an ellipse then the segmentation process ends and the system proceeds to the next step. Otherwise, the stroke is passed into two particle swarm algorithms that divides the stroke to either lines or lines and curves. The algorithms take the stroke points along with the possible dominant points $P_{pd}$ computed then produce a set of dominant points which are connected with either lines or curves (see fig. \ref{fig:Blockdiagram}). The next section describes the ellipse detection algorithm and the two particle swarm algorithms used to divide the stroke.\\
%Paragraphs describe the segmentation algorithm.  
\subsubsection{Ellipse Detection} 
%Describe the ellipse detection algorithms 
The process starts by computing the center of the stroke bounding box. The bounding box center point is used as the first estimation of the ellipse center. The axes of the ellipse are estimated as $width/2$ and $height/2$ of the stroke bounding box. The least square fitting algorithm is used to minimize the fitting error of the ellipse equation eq. \ref{eq:circleFit}.
\begin{equation}
E = \sum\limits_{i = 0}^N {\frac{{(x_i - x_0 )}}{{a^2 }}^2  + \frac{{(y_i - y_0 )}}{{b^2 }}^2  - 1} 
\label{eq:circleFit}
\end{equation} where $N$ is the number of points in the stroke, $a,b$ are the length of ellipse axes, $x_0$ , $y_0$ are the coordinates of the center point and $x_i$ \& $y_i$ are the coordinates of point $i$ in the stroke. After few loops, the error and a confidence values  are computed to check if the stroke can be labeled as ellipse or not.\\ %is computed to check if stroke is an ellipse. \\
%We found that if the confidante is above threshold then the probability of ellipse is highest otherwise the stroke is passed to the next section to get the divisions of stroke and test its error.  
\subsubsection{Discrete particle swarm algorithm (\textit{DPSO})}
\label{subsubsec:Discreteparticleswarmalgorithm}
Two DPSO algorithms are used to generate segmentations for each stroke the user draws. The segmentation with the minimum error value is chosen as the stroke segmentation. The problem definition is the same in both algorithms but they differ in the method they use to compute fitness and error functions.  
\subsubsection{Problem definition}
The input stroke with $N$ points can be represented by set $S = \left\{ {x_1 ,x_2  \ldots x_N } \right\}$ where $x_i$ is the location of the point $i$. The swarm algorithms consist of $M$ agents which are represented by the set 
$A  = \left\{ {P_i \left| {i = 1,2 \cdots M} \right.} \right\}$ where $P_i$ is a single solution particle from the solution space. Each particle decodes the problem with binary array with the same length $N$ as the input stroke.  
% The particles of the swarm represent a single solution of the solution space. For this problem the, each particle %will give a different segmentation for the input stroke. Firstly, we will define the stroke with N points by the set %S where.  We define the arc %An array with the same length as the number of points of the strokes.
Therefore, the system represents each particle $P_i$ by $P_i = \left\{ {p_{ij} \left| {j = 1,2 \cdots N} \right.} \right\}$ where $p_{ij}$ has only two values 0 or 1. When $p_{ij}=1$ means that point $j$ is a dominant point. 
% a!402B!
%$A = \left\{ {p_i \left| {i = 1,2 \cdots N} \right.} \right\}$
% a!402A!
%\begin{equation}
%A = \left\{ {p_i \left| {i = 1,2 \cdots N} \right.} \right\}.
%\end{equation}
\subsubsection{The algorithm}
The fitness function and error calculation are different in each of the two \textit{DPSO} algorithms. For the first algorithm \textsl{AlgS1}, 
 the arc $\widehat{x_ix_j}$ is defined as the consecutive set of points from point$x_i$ to point $x_{j}$ as in $x_i,x_{i+1} \cdots,x_j$. The line $\overline{x_i x_j} $ as the straight line connecting point $x_i$ to point $x_j$. The approximation error is computed by the equation \ref{eq:ErrorSwarm1}
\begin{equation}
E=\sum\nolimits_{i = 0}^M e ( \widehat{x_ix_{i+1}},\overline{x_i x_{i+1}})
\label{eq:ErrorSwarm1}
\end{equation} where $M$ is the number of dominant points in this solution. The error $e ( \widehat{x_ix_j},\overline{x_i x_j})$ is computed as the sum of squared perpendicular distance from every point along the arc $\widehat{x_ix_j}$ to the line $\overline{x_i x_j}$.  \\
The fitness is computed using equation \ref{eq:fitnessSwarm1}\begin{equation}
\max fitness(p_i ) = \left\{ {\begin{array}{*{20}c}
   { - E/\varepsilon N} & {ifE > \varepsilon ,}  \\
   {D/\sum\limits_{j = 1}^N {p_{ij} } } & {otherwise}  \\
\end{array}} \right.
\label{eq:fitnessSwarm1}
\end{equation} where $N$ is the number of points in the stroke, $D$ is the number of points in the solution that was previously labeled as a possible dominant point ($P_{pd}$), $E$ is the computed error and $\varepsilon$ is the error threshold. It should be noticed that when the error is larger than the threshold $E$ the fitness is given a -ve value to lower the value of solution. Otherwise the system favors the lower number of vertices.\\ %we will want to lower the number of vertices. \\
%if we say that s
%Alg1:
%Alg2: o
The second algorithm \textsl{AlgS2} has the same problem formulation but different fitness and error functions. It was previously introduced in \cite{CruveDivisionSwarm} but a genetic programming was used as the optimizing algorithm.  The error of both circle and line estimation are computed for each segment $S_i=\widehat{x_ix_j}$, the approximation with the lower error value is the chosen approximation of this segment $S_i$. The sum of the approximation error of all segments is the total error of the particle.  The error is computed by equation \ref{eq:errorSwarm2} \begin{equation}
E=\sum\nolimits_{i = 0}^M e(D_i) 
\label{eq:errorSwarm2}
\end{equation}where $M$ is the number of segments in the solution, $D_i$ is the minimum approximation error of curve and line approximations $min(d_c,d_l)$ as computed by \cite{CruveDivisionSwarm}.  The fitness is computed by the equation \ref{eq:fitnessSwarm2} \begin{equation}
\max fitness(P_i ) = \frac{1}{{E \times M^k }}
\label{eq:fitnessSwarm2}
\end{equation} where $E$ is the error and $M$ is the number of segments and $k$ is a parameter tweaked to get minimum number of segments. \\
%Describe how we used particle swarm in curve polygon approximation using first algorithm.  
%Describe how we used PSO in to divide stroke into segments and curves. 
%[These two algorithm was modified from the algorithm in paper \cite{PolygonApproximationPSO,CruveDivisionSwarm}].
\citeauthor{PolygonApproximationPSO} \cite{PolygonApproximationPSO} used a merge and divide algorithm after each loop of the swarm system to refine the solution but this paper is introducing another enhancement method. After each loop of the swarm algorithm (\textsl{AlgS1} and \textsl{AlgS2}), each particle is refined using the following procedure. For each particle $P_{ij}$ %loops on the set of selected dominant points to enhance the solution.
each dominant point is checked to find if it was labeled before as a \textit{possible dominant point} $P_{pd}$ (computed as in section \ref{Prepross}), if it is not labeled the point is moved to the nearest labeled point. After that the particles are tested to make sure that the distance between every two successive dominate point is larger than the constant $min_D$. If two points are found that they are nearer than $min_D$ then based on the decrease in the error $E$ in eq. \ref{eq:ErrorSwarm1} \& \ref{eq:errorSwarm2} one of the points are either removed or moved to the nearest possible dominate point. 
%check the new solution and check the new vertices if a vertex points is a possible dominant point it is left as a vertex. Otherwise, the system will search in the local neighborhood for the nearest possible dominant point to move these vertices to. After each change the error is computed and if new error is less that the old then the new set is approved. \\
\subsection{Recognition}
After the user draws all strokes of the symbol, he/she has to wait 10 seconds or press finish button beside the drawing area. The set of unrecognized strokes is grouped together along with their segmentation as input to the feature extraction process. A composite set of features is used to generate a single feature vector. The features used consist of Rubine feature set \cite{gestureexample12},  Zernike moments of order 21 \cite{HeloiseBeautification}, ink density \cite{GeometryAndDomain102} as well as some structural and spatial information like number of perpendiculars lines ,number of parallel lines and types of primitives in each symbol. After computing the features the symbol is introduced to the classifier. The system uses a support vector machine (SVM) classifier with Gaussian kernel (RBF kernel)\cite{libsvm}.\\%Some features like number of parallel, perpendicular and intersecting lines are computed from the segmentation other like density, centroid and Zernike moments are computed from the raw stroke points. 
 %trained with the 13 categories in the system. The same training set was used by \cite{HeloiseBeautification} in their symbol recognition system. \\ %  The table describe the features used in the system. 
%\begin{table}
%\begin{minipage}[t][1\totalheight]{0.3\columnwidth}
%
%\begin{tabular}{|l|l|l|}
%\hline 
%Type & Features & Notes\tabularnewline
%\hline 
%\hline Structural & No. of parallel lines & \tabularnewline
%\hline & No. of perpendicular lines & \tabularnewline
%\hline & No. of intersections & \tabularnewline
%\hline Statistical & Mean and standard deviation of the Curvature data   & \tabularnewline
%\hline & Mean of the speed data & \tabularnewline
%\hline 
%Rubine & Set of features \\for gesture recognition & Introduced by Rubine in \cite{} \tabularnewline
%\hline Zernike &  A Zernike\\ moments  &  Used by \cite{zernike61} \tabularnewline
%\hline Composite & width to\\ height ratio  & \tabularnewline
%\hline  & ink density  & Used by \cite{} \tabularnewline
%\hline
%\end{tabular}		
%\end{minipage}
%	\caption{Feature Table}
%	\label{tab:FeatureTable}
%\end{table}
  % Rubine el al.\cite{gestureexample12}  used a set of statistical features,  There are a lot of features used in the sketch recognition literature
%How to handle multi-stroked symbols. 
%The clustering algorithm.  
%The classifier used in recognition
%Describe the features used in recognition [ref to \cite{zernike61}]
\section{Experiments}\label{sec:Experiments}
A dataset collected by \citeauthor{HeloiseBeautification} is used to test the presented system\cite{HeloiseBeautification}. The data are drawn by 16 users each of them was asked to draw the 13 shapes from 30 to 50 times. Figure \ref{fig:symbolSet} shows a set of the shapes used in the data set. We divide the dataset into four sets each set contains four different users. We divide the dataset equally into training set and test set. To generate trusted results, four different splits for the training and test data are generated from the dataset. The results displayed are the recognition accuracy resulted from the classifier after recognizing the symbols. In the following section, the recognition accuracy means the average recognition accuracy in the four data splits. %The result presented in this section are the average result of the four splits. %then result are stored The results displayed are the recognition accuracy resulted from the classifier after recognizing the symbols. %Furthermore, each set is divided into train and test set where the trained set where used to train the classifiers and the test set where used for testing.  The algorithms are then tested using the four sets and the results are averaged. %We divide the dataset equally into training set and test set.  The results displayed are the recognition accuracy resulted from the classifier after recognizing the symbols. \\
%We divided the dataset into four sets each set contains four different users. Furthermore, each set is divided into train and test set where the trained set where used to train the classifiers and the test set where used for testing.  The algorithms are then tested using the four sets and the results are averaged.
\begin{figure}[]\centering
\fbox{  \parbox{3cm}{% 
		\includegraphics[scale=0.4]{images/symbolSet.pdf}	}}
	\caption{The Symbol Set} Ths figure shows a set of the symbols used in the dataset. 
	\label{fig:symbolSet}
\end{figure}
\begin{figure}[]
	\centering
		\includegraphics[scale=0.5]{images/test1.jpg}
	\caption{Algorithm comparison} The results of comparing the algorithms. The graphs displays the recognition rate of symbols. 
	\label{fig:test1}
\end{figure}
%In the figure \ref{fig:test1}, the accuracy means that final hit rate of all symbols used in the test set.by the  four datasets . 
We performed two experiments to test the system firstly we tested recognition accuracy of shapes in the data set with both algorithms (\textsl{AlgS1} and \textsl{AlgS2}). We also implemented the segmentation algorithm described in \cite{earlyprocess} (\textsl{Alg3}) to use as reference to our swarm algorithms.  Figure \ref{fig:test1} shows the accuracy achieved by each algorithm. The results shows that both \textit{DPSO} algorithms achieve better result than other algorithms. The swarm algorithms were tested with and without the ellipse detection module. The ellipse detection module appears to be superior to results with only the \textit{DPSO} algorithms.\\  

The second experiment we implemented is testing the effect of symbol complexity and type on the recognition rate. Figure \ref{fig:test2} shows the accuracy of each symbol, it is clearly noted that symbols that have only line segments achieve higher accuracy rate than other symbols. Figure \ref{fig:test2} also indicates that algorithm \textsl{AlgS1} alone achieve better performance than algorithm   \textsl{AlgS2} in the symbols that consist only of lines. This is natural as algorithm  \textsl{AlgS1} divides strokes into line segments only but \textsl{AlgS2} is able to divide strokes into lines and curves based on the minimum error of the segment itself. Algorithm \textsl{Alg3} gives good performance as long as the symbols consist of lines and curves, if the stroke consists of curve only  the algorithm may lead to wrong segmentation result. This is because the system divides the stroke first to line segments then tries to decide if each segment can be represent better as a curve unlike algorithm \textsl{AlgS2} where the curve segments are tested while choosing the best segmentation.  Combining both algorithm \textsl{AlgS1} and \textsl{AlgS2} improved the recognition rate of all symbols because of combining the advantages of both algorithms. The penalty for this increased performance is in the computational time needed to run both the swarm algorithms.  \\
\begin{figure*}[]
	\centering
		\includegraphics[scale=0.8]{images/test2.jpg}
	\caption{Symbols Comparison} The graph shows the recognition rate of each symbol using different algorithms. 
	\label{fig:test2}
\end{figure*}
%We could not test the result of the segmentation algorithm directly due to the fact that the correct segmentation is highly ambiguous. It is only based on what the user intends to draw while sketching the symbol. Figure \ref{fig:SampleSeg} shows a sample of the output of the segmentation block.  
  %The final experiment we performed was to test the efficiency svm classifier. We implemented the linear discriminator classifier described in \cite{gestureexample12}(see figure \ref{fig:test3}).  %The result shows that SVM is more scalable than the linear discriminator for this problem. %The test focus on the size of data needed to test each classifier and the achieved accuracy.  %For this experiment we also shows the classification time for both classifiers 
%\begin{figure}[]
%	\centering
% 
%				\subfigure[User strokes] {\includegraphics[scale=0.7]{images/strokebefore.jpg}}
%		 	\subfigure[Segmented strokes] {\includegraphics[scale=0.7]{images/strokeafter.jpg}}
%		 		\subfigure[Multiple symbols] {\includegraphics[scale=0.7]{images/results3.jpg}}
%		
%	\caption{Segmentation outputs} The figure shows sample of the output of the segmentation phase. Figure a) shows the stroke after the user draws it. The red points are points labeled as \textit{possible dominate points}. Figure b) shows the symbol after being segmented. Figure c) shows the segmentation of different and overlapped strokes. Notice the system mark the center of the ellipse that was identified.
%	\label{fig:SampleSeg}
%\end{figure}
%\begin{figure}[]
%	\centering
%		\includegraphics[scale=0.4,clip=true, viewport=0 380 700 1280]{images/test1.pdf}
%	\caption{The results of third experiment}
%	\label{fig:test3}
%\end{figure}
 %Details description of results got from comparing various algorithms  
 %Describe data set used for experiments ( No of data set, No. of categories, No of samples).
 %Describe other Algorithms [Alg 3 in paper \cite{earlyprocess}]used for comparing with the one described in the paper. 
\section{Conclusion and Future Work}
\label{ConclusionandFutureWork}
This paper presented a new approach to sketch recognition using PSO. The system uses both speed and curvature data which helps in improving the \textit{DPSO} algorithms over the original algorithms \cite{CruveDivisionSwarm,PolygonApproximationPSO}. It is noted that the \textit{DPSO}in general generates an optimized stroke segmentation which improves the final recognition rate.  The tradeoff between accuracy achieved and time complexity must be further investigated to achieve better results. The use of statistical moments and structural features improves the recognition rate. The system was tested on 13 different symbols and achieved satisfying results. The system dose not depends on low level recognizer but rather on a set of high level features. This makes the system easily expandable with aspect to symbols recognized. \\  
%As you can see form the experiments PSO have proved a spuriously than other system. 
%\section{Future Work}The next step in 
A possible extension of this research is to complete the clustering algorithm for fully automated sketch recognition. The clustering must be performed without the user explicit involvement. Other area of enhancements is the features extraction methods. Introducing more spatial and geometrical features is believed to improve classifications.  %Each new stroke is checked if it can be a symbol or is a part of already drawn un completed symbol. 
%\bibliography{Mybibliography}
\bibliography{../../neededfiles/Bibliographies/Mybibliography2}
\end{document}
